The present invention relates to a sequential type permutation apparatus which rearranges input data according to a specified rule to output the rearranged data in a digital integrated circuit.
A sequential type permutation apparatus is required in the stage of encoding or decoding digital VTR signals or in a similar case to sequentially change and restore the order of arrangement of a signal string according to a specified rule.
FIGS. 19A, 19B, 19C and 19D are charts showing examples of translation rules applied to a prior art sequential type permutation apparatus. These translation rules are for permutation of sixteen pieces of data grouped in one set, and according to the rules, the order of the successively inputted 16 pieces of data are changed before the data are outputted.
In this case, one piece of data is assumed to be, for example, an 8-bit binary number. Further, the above translation rules include two types 0 and 1, and switching of the translation rules is executed in response to an external designation. The order of the pieces of data inputted sequentially to the apparatus is changed (forward translation) according to the translation rule and then outputted. Further, the data the order of which has been changed according to the above translation rule, are restored to the original order (backward translation).
FIG. 18 shows a concrete circuit diagram of the aforementioned prior art sequential type permutation apparatus. This sequential type permutation apparatus has a first RAM (Random Access Memory) 2 and a second RAM 3 for temporary storage of data received from a data input terminal 1. Sequentially inputted pieces of data are written to the first RAM 2 or the second RAM 3 at respective locations according to the translation rule, and thereafter those pieces of data are sequentially read out from the piece of data written at the location having address 0. Thus, the resulting data, the order of which has been changed are outputted from a data output terminal 4.
That is, in the sequential type permutation apparatus, random access conforming to the translation rule is executed in the stage of writing to the RAMs 2 and 3, and a sequential access (access in the increasing order from the address 0) is executed in the stage of reading from the RAMs 2 and 3.
It is to be noted that the same result can be obtained by executing a sequential access in the stage of writing into the RAMs 2 and 3 and executing a random access conforming to the translation rule in the stage of reading from the RAMs 2 and 3.
An address translation table memory 5 is composed of a read only memory in which are written four types of translation tables 0-0, 0-1, 1-0 and 1-1 formed by tabulating the translation rules 0 and 1 shown in FIGS. 19A and 19B and FIGS. 19C and 19D. In each translation table are listed the "order numbers in the input stage" and the "order numbers in the output stage" which are paired with each other. When an input address equal to an "order number in the input stage" is given from an address input terminal 18 to an input address bus 12, the corresponding "order number in the output stage" is outputted to a translated address bus 9.
The translation table 0-0 reflects the translation rule 0 for forward translation. The translation table 0-1 reflects the translation rule 0 for backward translation. The translation table 1-0 reflects the translation rule 1 for forward translation. The translation table 1-1 reflects the translation rule 1 for backward translation. In either case of the translation tables, the "order number in the output stage" (i.e., translated address associated with the input address) is given as a write address via the translated address bus 9 to the RAM 2 or 3 into which data are about to be written. At the same time, the input address is given as a read address via the input address bus 12 to the RAM 3 or 2 from which data are about to be read.
Then, a translation table of the address translation table memory 5 is designated by an output signal SELTLP from a table selection input terminal 19 and an output signal SELFBP from a forward/backward translation selection terminal 20. Specifically, as shown in FIG. 20A, the translation rule 0 is designated when the output signal SELTLP of the table selection input terminal 19 has a logical level of "0", and the translation rule 1 is designated when the output signal SELTLP has a logical level of "1". Further, as shown in FIG. 20B, the forward translation is designated when the output signal SELFBP of the forward/backward translation selection terminal 20 has a logical level of "0", and the backward translation is designated when the output signal SELFBP has a logical level of "1".
Therefore, when a combination (x, y) of the logical level x of the output signal SELTLP of the table selection input terminal 19 and the logical level y of the output signal SELFBP of the forward/backward translation selection terminal 20 is (0, 0), the translation table 0-0 is designated. Similarly, the translation table 0-1 is designated in the case of (0, 1), the translation table 1-0 is designated in the case of (1, 0) and the translation table 1-1 is designated in the case of (1, 1).
Such a plurality of required translation rules are each stored in a table form in the address translation table memory 5 and the required translation table is read from the address translation table memory 5 every time of translation, for it is desired to execute the translation according to a varied translation rule depending on the type of the data.
When the logical level of a signal SELWMP from a write memory selection terminal 7 is "1" (i.e., when the first RAM 2 is selected for data writing and the second RAM 3 is selected for data reading), a first selector 8 selects the signal on the translated address bus 9 and outputs it to a first node 10 as a signal ADRSP1. On the other hand, a second selector 11 selects the signal on the input address bus 12 and outputs it to a second node 13 as an address ADRSP2. In contrast to this, when the logical level of the signal SELWMP from the write memory selection terminal 7 is "0" (i.e., when the second RAM 3 is selected for data writing and the first RAM 2 is selected for data reading), the first selector 8 selects the signal on the input address bus 12 and outputs it to the first node 10 as the signal ADRS1. On the other hand, the second selector 11 selects the signal on the translated address bus 9 and outputs it to the second node 13 as the signal ADRS2.
When an output signal SELRMP from a read memory selection terminal 14 has a logical level of "1" (i.e., when the second RAM 3 is selected for data reading and the first RAM 2 is selected for data writing), a third selector 15 connects a fourth node 17 to the data output terminal 4. In contrast to this, when the output signal SELRMP has a logical level of "0" (i.e., when the first RAM 2 is selected for data reading and the second RAM 3 is selected for datA writing), a third selector 15 connects a third node 16 to the data output terminal 4.
The permutation of the input data executed by the sequential type permutation apparatus shown in FIG. 18 will be described below with reference to FIGS. 21A through 21F showing signal change.
The RAMs 2 and 3 can each store therein sixteen pieces of data. Data are input in sets each of sixteen pieces from the data input terminal 1 in synchronization with a clock supplied from a clock input terminal 6.
First, when the logical level of the signal SELWMP from the write memory selection terminal 7 becomes "1", the sixteen pieces of data of a first set (IDATAP) from the data input terminal 1 are written into the first RAM 2. Subsequently, the logical levels of the signals SELWMP and SELRMP from the write memory selection terminal 7 and the read memory selection terminal 14 become "0". Then, the sixteen pieces of data of a second set (IDATAP) supplied from the data input terminal 1 are written into the second RAM 3. Meanwhile, the sixteen pieces of data of the first set are successively read from the first RAM 2 and transmitted to the data output terminal 4 as signal ODATAP. Subsequently, the logical levels of the signals SELWMP and SELRMP from the write memory selection terminal 7 and the read memory selection terminal 14 become "1". Then, the sixteen pieces of data of a third set (IDATAP) from the data input terminal 1 are written into the first RAM 2. In the meantime, the sixteen pieces of data of the second set are successively read from the second RAM 3 and transmitted to the data output terminal 4 as signal ODATAP.
The above operations are repeated subsequently.
Consequently, as shown in FIGS. 21A through 21F, random data write and sequential data read are alternately executed on the first RAM 2. Further, sequential data read and random data write are alternately executed on the second RAM 3 inversely in phase to the first RAM 2. Further, the data read from the second RAM 3 and the data read from the first RAM 2 are alternately outputted to the data output terminal 4.
As described above, in the prior art sequential type permutation apparatus, the translation table to be used is designated based on the output signal SELTLP of the table selection input terminal 19 and the output signal SELFBP of the forward/backward translation selection terminal 20, and address values "0" through "15" are sequentially inputted from the address input terminal 18 into the apparatus. Consequently, the address signal representative of a value same as the "order number in the input stage" in the designated translation table is supplied to the input address bus 12 sequentially from "0", while the corresponding "order number in the output stage" in the designated translation table is outputted to the translated address bus 9.
Then, according to the signal SELWMP from the write memory selection terminal 7, the selector 8 or 11 corresponding to the RAM 2 or 3 for writing transmits the "order number in the output stage" on the translated address bus 9 as the write address to the RAM 2 or 3. On the other hand, the selector 11 or 8 corresponding to the RAM 3 or 2 for reading transmits the input address on the input address bus 12 as the read address to the RAM 3 or 2.
FIG. 22 is a diagram showing a part of the internal construction of the RAM 2 (RAM 3 has the same internal construction although not illustrated). In each RAM 2, 3, the input address (read address) signal or the translated address (write address) signal transmitted from the selector 8, 11 to an address bus 21 is decoded by a decoder 22. Then, according to the decoding result, one of word lines 23 is activated. Then, data are written into or read from the activated word with the aid of bit lines 24, . . . , 24.
In the sequential type permutation apparatus shown in FIG. 18, sets of 16 pieces of data, each piece of data consisting of 8 bits, are written into or read from the first and second RAMs 2 and 3 set by set, and therefore, the RAMs 2 and 3 are each comprised of sixteen words in which the 8-bit data are stored. Accordingly, there are sixteen word lines 23 and eight bit lines 24. Furthermore, since it is required to individually designate the sixteen words in each RAM 2 and 3, the address bus 21 is required to have signal lines corresponding to four bits.
The data thus read from the RAM 2 or 3 are outputted to the data output terminal 4 connected by the third selector 15 in response to the signal SELRMP from the read memory selection terminal 14.
It is known that depending on the characteristics of the translation rule, the first RAM 2 and the second RAM 3 shown in FIG. 18 can be constructed of a single RAM by means of a dual port memory which has a first port and a second port and has a storage capacity corresponding to the data of one set, as disclosed in Japanese Patent Laid-Open Publication No. HEI 5-207289.
FIG. 23 shows a diagram of the construction of a dual port memory disclosed in the Japanese Patent Laid-Open Publication No. HEI 5-207289.
In this dual port memory 25, input data at a first port 26a is written according to a write address inputted to a write address input terminal 27. Then, the written data are read through a second port 26b according to a read address inputted to a read address input terminal 28. In this case, the read address is generated by a read address generator 30 based on a write address signal delayed by a specified time in a delay section 29.
Next, the case where the dual port memory 25 shown in FIG. 23 is applied to the sequential type permutation apparatus shown in FIG. 18 will be discussed below.
A sequential type permutation apparatus using the dual port memory 25 may be achieved by employing the following arrangement. That is, input data at the data input terminal 1 shown in FIG. 18 is inputted to the first port 26a of the dual port memory 25, while an input address signal at the address input terminal 18 is inputted to the write address input terminal 27. Further, the input address signal is delayed and then given to the address translation table memory 5, and the outputted translated address is supplied to the read address input terminal 28 of the dual port memory 25. Then, the data read from the second port 26b of the dual port memory 25 is transmitted to the data output terminal 4.
Therefore, this sequential type permutation apparatus has a sequential write and random read function, which is converse to the random write and sequential read function of the sequential type permutation apparatus shown in FIG. 18, although the order of the data outputted after the permutation is identical.
FIG. 24 shows the transitions of the read address for a first set of data, the write address for a second set of data, and the read address for the second set of data in the case where the permutation is executed with the translation table 0-0 shown in FIG. 19A by means of the sequential type permutation apparatus employing the dual port memory 25.
As is apparent from FIG. 24, in the case of the permutation based on the translation table 0-0 by means of the dual port memory 25, the data written in the dual port memory 25 can be read without being destroyed when the aforementioned delay is of seven to nine clocks. FIG. 24 shows the case where the delay corresponds to eight clocks.
The above-described various prior art sequential type permutation apparatuses have the following problems.
Problems of the first sequential type permutation apparatus having two RAMs shown in FIG. 18 will be described first.
(1) The translation tables are used exclusively for the forward translation and the backward translation, respectively. That is, for a single translation rule, two translation tables are required to be stored in the address translation table memory 5. Therefore, when there are two types of translation rules of the translation rule 0 and the translation rule 1, it is necessary to store four (two by two) translation tables.
Meanwhile, the forward translation and the backward translation are performed only by reading the same translation rule in opposite directions to each other. Therefore, it may be sufficient to store either the forward translation table or the backward translation table. In other words, in the prior art sequential type permutation apparatus, the address translation table memory 5 stores even basically unnecessary translation tables, so that its storage capacity becomes larger than is necessary.
(2) Each of the two selectors 8 and 11 selects either the "order number in the output stage (write address)" on the translated address bus 9 or the input address (read address) on the input address bus 12 according to the signal from the write memory selection terminal 7. Therefore, it is necessary to wire two address buses of the translated address bus 9 and the input address bus 12 up to the two selectors 8 and 11.
In general, the bus in an integrated circuit has a long wiring length and needs a large layout area, and this results in an increased load capacity. Therefore, a great power is required for transmitting a signal via the long bus. Accordingly, it is preferable to make the bus length as short as possible. In the case of the prior art apparatus, each of the RAMs 2 and 3 requires only either of the write address from the translated address bus 9 and the read address from the input address bus 12 in the writing stage and the reading stage. Furthermore, as described above, the write address (order number in the output stage) and the read address (input address) correspond to each other on a one-to-one basis on the translation table. Therefore, the write address may be derived from the read address, and it may be sufficient to form only the input address bus 12. In other words, due to the formation of the basically unnecessary translated address bus 9, the prior art sequential type permutation apparatus needs a bus length longer than necessary, a circuit area larger than necessary, power consumption greater than necessary.
In the case of the sequential type permutation apparatus using the dual port memory 25 of FIG. 23 having a capacity corresponding to one set of data in place of the two RAMs 2 and 3 of the sequential type permutation apparatus of FIG. 18 to attempt to reduce the data storage capacity, the following problem occurs.
When considering the case where an output is made by merely changing the order of the input data of one set, it is sufficient to provide a dual port memory 25 having a capacity corresponding to one set of data as disclosed in Japanese Patent Laid-Open Publication No. HEI 5-207289 and start the read before the write of one set of data into the dual port memory 25 is completed.
As well known, in recent years, the digital techniques of electronic equipment have progressed, and among others, a band compression technique intended for coding image data at a low bit rate for transmission and recording has made a remarkable progress. As the band compression technique, there has been developed a variety of systems such as a predictive coding system and an orthogonal coding system (refer to "Multi-dimensional Processing of TV image", T. Fukinuki, published by NIKKAN KOGYO SHIMBUN, LTD, Japan).
Currently, the technique of band-compressing digital image processing data has been standardized. According to the standardization, one set of quantization coefficients arranged raster-sequentially is permutated or rearranged in a zigzag order, and a quantizing process is executed based on the quantization coefficients that have undergone the permutation.
The quantizing process is a sort of information omitting, or rounding off process, and to efficiently perform the quantizing process, it is necessary to determine a maximum value among the input data in one set. Therefore, the quantizing process cannot be executed unless the maximum value of the input data in one set has been determined when the rearranged, or permutated data are outputted from the sequential type permutation apparatus.
The above fact is not limited to the case where the quantization follows a processing performed by the sequential type permutation apparatus, and then, information required to be obtained from the input data in one set is not necessarily a maximum value. In general, there are also cases where, according to the subsequent processing, a minimum value among the input data in one set must be determined or a total of the input data in one set must be obtained. In such cases also, the necessary information of input data in one set is required to have been already obtained when the data having undergone the permutation are outputted from the sequential type permutation apparatus.
That is, the data reading from the sequential type permutation apparatus must be started at least after all the data in one set have been written into the memory.
Therefore, in the sequential type permutation apparatus which employs the dual port memory 25 shown in FIG. 23 in place of the two RAMs 2 and 3 of the sequential type permutation apparatus shown in FIG. 18, when the reading of one set of data is started before the completion of the writing of the one set of data into the dual port memory 25, the read data must be stored in another memory until necessary information such as a maximum or minimum value has been obtained from the one set of input data such that the next processing will be able to start. This, however, cancels the effect of using the dual port memory 25 to reduce the memory capacity of the sequential type permutation apparatus of FIG. 18.
So long as the above restriction is placed on the timing of reading data from the dual port memory 25 of the sequential type permutation apparatus, the mere replacement of the two RAMs 2 and 3 of the sequential type permutation apparatus shown in FIG. 18 with the dual port memory 25 of FIG. 23 having a capacity corresponding to one set of data will not able to realize a sequential type permutation apparatus with a dual port memory which is capable of dealing with a plurality of translation rules even considering the subsequent process.